//
// Created by Lenovo on 2024/2/29.
//
#include<bits/stdc++.h>
using namespace std;
//跳跃游戏2
class Solution {
public:
    //dp
    int jump1(vector<int>& nums) {
        vector<int> dp(10010);     //dp[i]表示到达i位置所需要的最少跳跃次数
        for(int i=0;i<nums.size();i++) dp[i]=i;
        for(int i=0;i<nums.size();i++){
            for(int j=1;j<=nums[i];j++){
                dp[i+j]=min(dp[i]+1,dp[i+j]);
            }
        }
        return dp[nums.size()-1];
    }

    //贪心
    int jump2(vector<int>& nums) {
        if(nums.size()==1) return 0;
        int curMaxDistance=0;       //当前能到达的最远距离
        int ans=0;                  //返回结果
        int nextMaxDistance=0;      //下一步能到达的最远距离
        for(int i=0;i<nums.size();i++){
            nextMaxDistance=max(nextMaxDistance,i+nums[i]);         //更新下一步最远距离
            if(i==curMaxDistance){                                  //到达当前最远距离
                ans++;                                              //步数+1
                curMaxDistance=nextMaxDistance;                     //更新当前最远距离
                if(nextMaxDistance>=nums.size()-1)                  //当前最远距离覆盖了终点
                    break;
            }
        }
        return ans;
    }
};